package leetcode.hot100;

import java.util.HashMap;

public class Solution146 {

    public static void main(String[] args) {
        LRUCache lRUCache = new LRUCache(2);
        lRUCache.put(2,1);
        System.out.println(lRUCache.hashMap);
        lRUCache.put(1,1);
        System.out.println(lRUCache.hashMap);
        lRUCache.put(2,3);
        System.out.println(lRUCache.hashMap);
        lRUCache.put(4,1);
        System.out.println(lRUCache.hashMap);
        System.out.println(lRUCache.get(1));
        System.out.println(lRUCache.get(2));
    }


}


class LRUCache {

    int capacity;
    Node head;
    HashMap<Integer,Node> hashMap;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.head = new Node(-1,-1);
        head.preNode = head;
        head.nextNode = head;
        this.hashMap = new HashMap<>();
    }

    public int get(int key) {
        if(!hashMap.containsKey(key)) return -1;
        //把当前Node移到双端链表尾巴,表示刚刚使用过
        Node node = hashMap.get(key);
        //删掉,走之前料理后事
        deleteNode(node);
        //插到末尾，建立新的关系
        insertToTail(node,head);
        //返回node的值
        return node.value;
    }

    public void put(int key, int value) {
        //先查看有没有key
        if(hashMap.containsKey(key)){
            Node node = hashMap.get(key);
            node.value = value;
            deleteNode(node);
            insertToTail(node,head);
        }else {
            //查看缓存满了没有
            if(hashMap.size()==capacity){
                //需要删除最久没使用的
                Node delNode = head.nextNode;
                deleteNode(delNode);
                hashMap.remove(delNode.key);
            }
            //不满或者删除后，将新节点直接插到尾部
            Node newNode = new Node(key,value);
            insertToTail(newNode,head);
            hashMap.put(key,newNode);
        }
    }

    public void insertToTail(Node node, Node head){
        //head是双端循环队列的头部
        Node last = head.preNode;
        last.nextNode = node;
        node.preNode = last;
        head.preNode = node;
        node.nextNode = head;
    }

    public void deleteNode(Node node){
        node.preNode.nextNode = node.nextNode;
        node.nextNode.preNode = node.preNode;
    }
}

class Node{

    Node preNode, nextNode;
    int key, value;

    public Node(int key, int value){
        this.key = key;
        this.value = value;
        this.preNode = null;
        this.nextNode = null;
    }
}